import java.util.*;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i=0;
        int j=0;
        List<Integer>list=new ArrayList<>();
        while(i<nums1.length&&j< nums2.length){
            if(nums1[i]<nums2[j]){
                i++;
            } else if (nums1[i]>nums2[j]) {
                j++;
            }else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        int index=0;
        int[] nums=new int[list.size()];
        for(int k=0;k<list.size();k++){
            nums[index++]=list.get(k);
        }
        return nums;
    }


    public int maxProfit(int[] prices) {
        int minprice=Integer.MAX_VALUE;
        int maxprofit=0;
        for (int i = 0; i <prices.length; i++) {
            if(prices[i]<minprice){
                minprice=prices[i];
            } else if (prices[i]-minprice>maxprofit) {
                maxprofit=prices[i]-minprice;
            }
        }
        return maxprofit;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>ans=new ArrayList<TreeNode>();
        if(n==0){
            return ans;
        }
        return getAns(1,n);
    }
    //递归函数
    private List<TreeNode>getAns(int start,int end){
        List<TreeNode>ans=new ArrayList<TreeNode>();
        //start ——> 需要递归开始的位置   end ——> 需要递归的尾巴
        if(start>end){
            ans.add(null);
            return ans;
        }
        //说明正好递归结束
        if(start==end){
            TreeNode tree=new TreeNode(start);
            ans.add(tree);
            return ans;
        }

        for(int i=start;i<=end;i++){
            List<TreeNode>leftTrees=getAns(start,i-1);
            List<TreeNode>rightTrees=getAns(i+1,end);
            //遍历元素将元素加入到ans中
            for(TreeNode leftTree:leftTrees){
                for(TreeNode rightTree:rightTrees){
                    TreeNode root=new TreeNode(i);
                    root.left=leftTree;
                    root.right=rightTree;
                    ans.add(root);
                }
            }
        }return ans;
    }






}